package com.zhugang.week13.binarysearch;

/**
 * @program algorithms
 * @description: binarySearch
 * @author: chanzhugang
 * @create: 2022/11/24 23:38
 */
public class BinarySearch {

    /**
     * 标准二分查找, 直接套模版
     * 非递归写法
     *
     * @param a
     * @param n
     * @param value
     * @return
     */
    public int bsearch(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (a[mid] == value) {
                return mid;
            } else if (a[mid] < value) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 递归写法
     *
     * @param a
     * @param n
     * @param value
     * @return
     */
    public int bsearch2(int[] a, int n, int value) {
        return bsearch_(a, 0, n - 1, value);
    }

    private int bsearch_(int[] a, int low, int high, int value) {
        if (low > high) {
            return -1;
        }
        int mid = low + (high - low) / 2;
        if (a[mid] == value) {
            return mid;
        } else if (a[mid] < value) {
            return bsearch_(a, mid + 1, high, value);
        } else {
            return bsearch_(a, low, mid - 1, value);
        }
    }
}